package cn.genmer.test.security.leetcode;

import java.util.Arrays;

/**
 * 1011. 在 D 天内送达包裹的能力
 * 传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。
 *
 * 传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。
 *
 * 返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。
 *
 *
 *
 * 示例 1：
 *
 * 输入：weights = [1,2,3,4,5,6,7,8,9,10], D = 5
 * 输出：15
 * 解释：
 * 船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示：
 * 第 1 天：1, 2, 3, 4, 5
 * 第 2 天：6, 7
 * 第 3 天：8
 * 第 4 天：9
 * 第 5 天：10
 *
 * 请注意，货物必须按照给定的顺序装运，因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。
 * 示例 2：
 *
 * 输入：weights = [3,2,2,4,1,4], D = 3
 * 输出：6
 * 解释：
 * 船舶最低载重 6 就能够在 3 天内送达所有包裹，如下所示：
 * 第 1 天：3, 2
 * 第 2 天：2, 4
 * 第 3 天：1, 4
 * 示例 3：
 *
 * 输入：weights = [1,2,3,1,1], D = 4
 * 输出：3
 * 解释：
 * 第 1 天：1
 * 第 2 天：2
 * 第 3 天：3
 * 第 4 天：1, 1
 *
 *
 * 提示：
 *
 * 1 <= D <= weights.length <= 5 * 104
 * 1 <= weights[i] <= 500
 */
public class AbilityServicePackage {
    public static void main(String[] args) {
        int[] weights1 = new int[]{1,2,3,4,5,6,7,8,9,10};
        int[] weights2 = new int[]{3,2,2,4,1,4};
        int[] weights3 = new int[]{1,2,3,1,1};
        System.out.println("示例1的最低载重为: 15, 计算结果为:" + shipWithinDays3(weights1, 5));
        System.out.println("示例2的最低载重为: 6, 计算结果为:" + shipWithinDays3(weights2, 3));
        System.out.println("示例3的最低载重为: 3, 计算结果为:" + shipWithinDays3(weights3, 4));
    }


    public static int shipWithinDays(int[] weights, int days) {

        // 0. 找出数组中最大的值(单个货物最大重量) max和总重量 totalWeight
        int max = 0;
        int total = 0;
        for (int w: weights){
            total += w;
            max = Math.max(max, w); int r = (int)1e8;
        }
        // 1. 如果最大值*days > 总重量 - 直接返回单个重量
        if (max * days > total){
            return max;
        } else {
            // 2. 如果最低载重超过单个最重
            // ... 除了遍历,没想到啥高效的方法
        }
        return max;
    }
    /**
     * 二分解法（精确边界）
     * 假定「D 天内运送完所有包裹的最低运力」为 ans，那么在以 ans 为分割点的数轴上具有「二段性」：
     *
     * 数值范围在 (-\infty, ans)(−∞,ans) 的运力必然「不满足」 D 天内运送完所有包裹的要求
     * 数值范围在 [ans, +\infty)[ans,+∞) 的运力必然「满足」 D天内运送完所有包裹的要求
     * 即我们可以通过「二分」来找到恰好满足 D天内运送完所有包裹的分割点 ans。
     *
     * 接下来我们要确定二分的范围，由于不存在包裹拆分的情况，考虑如下两种边界情况：
     *
     * 理论最低运力：只确保所有包裹能够被运送，自然也包括重量最大的包裹，此时理论最低运力为 max，max 为数组 weights 中的最大值
     * 理论最高运力：使得所有包裹在最短时间（一天）内运送完成，此时理论最高运力为 sum，sum 为数组 weights 的总和
     * 由此，我们可以确定二分的范围为 [max, sum][max,sum]。
     *
     *  看不懂的版本, 变量好乱
     *
     * 作者：AC_OIer
     * 链接：https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days/solution/gong-shui-san-xie-li-yong-er-duan-xing-z-95zj/
     * @return
     */
    public int shipWithinDays2(int[] weights, int days) {
        int max = 0, sum = 0;
        int left = max, right = sum;
        while (left < right) {
            int mid = left + right >> 1;
            if (check(weights, mid, days)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return right;
    }

    /**
     *
     * @param ws 包裹重量数组
     * @param mid 临时的载重量
     * @param days
     * @return
     */
    boolean check(int[] ws, int mid, int days) {
        // 包裹数量
        int length = ws.length;
        // 当前假设载重量[mid]前提下, 需要的天数
        int needs = 1;
        // sum: 当前船上已装包裹重量和
        for (int i = 1, sum = ws[0]; i < length; sum = 0, needs++) {
            while (i < length && sum + ws[i] <= mid) {
                sum += ws[i];
                i++;
            }
        }
        // 计算的天数如果比需要的天数小
        return needs - 1 <= days;
    }

    /**
     * 官方重写
     * 思路与算法
     *
     * 假设当船的运载能力为 xx 时，我们可以在 \textit{days}days 天内运送完所有包裹，那么只要运载能力大于 xx，我们同样可以在 \textit{days}days 天内运送完所有包裹：我们只需要使用运载能力为 xx 时的运送方法即可。
     *
     * 这样一来，我们就得到了一个非常重要的结论：
     *
     * 存在一个运载能力的「下限」x_\textit{ans}x
     * ans
     * ​
     *  ，使得当 x \geq x_\textit{ans}x≥x
     * ans
     * ​
     *   时，我们可以在 \textit{days}days 天内运送完所有包裹；当 x < x_\textit{ans}x<x
     * ans
     * ​
     *   时，我们无法在 \textit{days}days 天内运送完所有包裹。
     *
     * 同时，x_\textit{ans}x
     * ans
     * ​
     *   即为我们需要求出的答案。因此，我们就可以使用二分查找的方法找出 x_\textit{ans}x
     * ans
     * ​
     *   的值。
     *
     * 在二分查找的每一步中，我们实际上需要解决一个判定问题：给定船的运载能力 xx，我们是否可以在 \textit{days}days 天内运送完所有包裹呢？这个判定问题可以通过贪心的方法来解决：
     *
     * 由于我们必须按照数组 \textit{weights}weights 中包裹的顺序进行运送，因此我们从数组 \textit{weights}weights 的首元素开始遍历，将连续的包裹都安排在同一天进行运送。当这批包裹的重量大于运载能力 xx 时，我们就需要将最后一个包裹拿出来，安排在新的一天，并继续往下遍历。当我们遍历完整个数组后，就得到了最少需要运送的天数。
     *
     * 我们将「最少需要运送的天数」与 \textit{days}days 进行比较，就可以解决这个判定问题。当其小于等于 \textit{days}days 时，我们就忽略二分的右半部分区间；当其大于 \textit{days}days 时，我们就忽略二分的左半部分区间。
     *
     * 细节
     *
     * 二分查找的初始左右边界应当如何计算呢？
     *
     * 对于左边界而言，由于我们不能「拆分」一个包裹，因此船的运载能力不能小于所有包裹中最重的那个的重量，即左边界为数组 \textit{weights}weights 中元素的最大值。
     *
     * 对于右边界而言，船的运载能力也不会大于所有包裹的重量之和，即右边界为数组 \textit{weights}weights 中元素的和。
     *
     * 我们从上述左右边界开始进行二分查找，就可以保证找到最终的答案。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days/solution/zai-d-tian-nei-song-da-bao-guo-de-neng-l-ntml/
     * @param weights
     * @param days
     * @return
     */
    public static int shipWithinDays3(int[] weights, int days) {
        // 其实就是确定一个中间量作为假设载重量, 然后将其需要的天数与要求天数的对比来选择区间
        // 确定二分查找左右边界
        int left = Arrays.stream(weights).max().getAsInt();
        int right = Arrays.stream(weights).sum();
        while (left < right){
            // 二分结果中间点 - 就是假设,现在的载重量
            int mid = (left+right) >> 1;
            // 假设当前船上的包裹累计重量 || 需要的天数,最低1天
            int cur = 0, needs = 1;
            for (int wight: weights){
                // 当累积货物超过现在假设的载重量时
                if (cur + wight > mid){
                    // 需要的天数 + 1
                    needs ++;
                    // 重置当前船的重量, 因为下一艘了
                    cur = 0;
                }
                cur += wight;
            }
            // 如果需要的天数比要求的少, 说明载重量并不是要求的最低载重量, 区间范围缩小为左半部分
            if (needs <= days){
                right = mid;
            } else {
                // 如果需要的天数比要求的多, 说明载重量小了, 区间范围缩小为右半部分
                left = mid + 1;
            }
        }
        return left;
    }
    }
